/*************************************************************************
 * File Name:    Candy.cc
 * Author:       zero91
 * Mail:         jianzhang9102@gmail.com
 * Created Time: Wed 30 Oct 2013 10:31:16 PM CST
 * 
 * Description:  
 |-----------------------------------------------------------------------
 | Problem: Candy Total
 | There are N children standing in a line. Each child is assigned a rating value.
 |
 | You are giving candies to these children subjected to the following requirements:
 |
 | Each child must have at least one candy.
 | Children with a higher rating get more candies than their neighbors.
 | What is the minimum candies you must give?
 |------------------------------------------------------------------------
 ************************************************************************/

#include <iostream>
#include <fstream>
#include <sstream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <deque>
#include <map>
#include <set>
#include <functional>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <iomanip>

using namespace std;

class Solution {
public:
    int candy(vector<int> &ratings) {
        if (ratings.size() == 0) return 0;
        
        vector<pair<int, int> > val(ratings.size(), pair<int, int>(1,1));
        
        for (size_t i = 1; i < ratings.size(); ++i) {
            if (ratings[i] > ratings[i - 1]) val[i].first = val[i - 1].first + 1;
            else val[i].first = 1;
        }
        
        for (int i = ratings.size() - 2; i >= 0; --i) {
            if (ratings[i] > ratings[i + 1]) val[i].second = val[i + 1].second + 1;
            else val[i].second = 1;
        }
        
        int ans = 0;
        for (size_t i = 0; i < ratings.size(); ++i) {
            ans += max(val[i].first, val[i].second);
        }
        return ans;
    }
};
